/*
 * Copyright 2012 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License,
 * version 2.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at:
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */

package io.netty.buffer;

final class PoolSubpage<T> implements PoolSubpageMetric {

  final PoolChunk<T> chunk;
  private final int memoryMapIdx;
  private final int runOffset;
  private final int pageSize;
  private final long[] bitmap;

  PoolSubpage<T> prev;
  PoolSubpage<T> next;

  boolean doNotDestroy;
  int elemSize;
  private int maxNumElems;
  private int bitmapLength;
  private int nextAvail;
  private int numAvail;

  // TODO: Test if adding padding helps under contention
  //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;

  /**
   * Special constructor that creates a linked list head
   */
  PoolSubpage(int pageSize) {
    chunk = null;
    memoryMapIdx = -1;
    runOffset = -1;
    elemSize = -1;
    this.pageSize = pageSize;
    bitmap = null;
  }

  /**
   * 这里其实就是创建一个PoolSubpage，首先每个PoolSubpage占用的内存是由pageSize指定的，默认为8KB。我们前面讲过，
   * 对于tiny和small类型的，都是由一个PoolSubpage的数组组成的，数组的每个元素所存储的数据元素的大小也是不一样的，
   * 比如对于tiny类型1号位的存储的大小为16字节，二号位存储的大小为32字节。这里的elemSize其实就是指定了当前PoolSubpage
   * 将要存储的大小，比如这里的16和32，并且其会对应到其不同的PoolSubpage[]数组的不同位置。
   * 在构建PoolSubpage的时候会计算该对象中可以存储的元素的个数，比如
   * maxNumElems指定了最多可存储的元素个数；
   * numAvail指定了还有多少个元素可用
   * nextAvail指定了下一个可用的元素的位置
   *
   * bitmap，对于tiny类型该字段是一个长度为8的数组，该字段的含义其实是其每一个元素的每一个字节都表示某个位置的16个字节是否已经被使用了
   *         由于一个long占64字节，8个long就是512，而其每个字节都表示一段16KB的内存是否被使用，因而总共可以表示的内存为8KB，
   *         也就是这里的pageSize
   */
  PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int memoryMapIdx, int runOffset, int pageSize, int elemSize) {
    this.chunk = chunk;
    this.memoryMapIdx = memoryMapIdx;
    this.runOffset = runOffset;
    this.pageSize = pageSize;
    bitmap = new long[pageSize >>> 10]; // pageSize / 16 / 64
    init(head, elemSize);
  }

  // elemSize指定了目标获取的字节数
  void init(PoolSubpage<T> head, int elemSize) {
    doNotDestroy = true;
    this.elemSize = elemSize;
    if (elemSize != 0) {
      maxNumElems = numAvail = pageSize / elemSize;
      nextAvail = 0;
      bitmapLength = maxNumElems >>> 6;
      if ((maxNumElems & 63) != 0) {
        bitmapLength++;
      }

      for (int i = 0; i < bitmapLength; i++) {
        bitmap[i] = 0;
      }
    }
    addToPool(head);
  }

  /**
   * Returns the bitmap index of the subpage allocation.
   */
  long allocate() {
    if (elemSize == 0) {
      return toHandle(0);
    }

    if (numAvail == 0 || !doNotDestroy) {
      return -1;
    }

    final int bitmapIdx = getNextAvail();
    int q = bitmapIdx >>> 6;
    int r = bitmapIdx & 63;
    assert (bitmap[q] >>> r & 1) == 0;
    bitmap[q] |= 1L << r;

    if (--numAvail == 0) {
      removeFromPool();
    }

    return toHandle(bitmapIdx);
  }

  /**
   * @return {@code true} if this subpage is in use. {@code false} if this subpage is not used by
   * its chunk and thus it's OK to be released.
   */
  boolean free(PoolSubpage<T> head, int bitmapIdx) {
    if (elemSize == 0) {
      return true;
    }
    int q = bitmapIdx >>> 6;
    int r = bitmapIdx & 63;
    assert (bitmap[q] >>> r & 1) != 0;
    bitmap[q] ^= 1L << r;

    setNextAvail(bitmapIdx);

    if (numAvail++ == 0) {
      addToPool(head);
      return true;
    }

    if (numAvail != maxNumElems) {
      return true;
    } else {
      // Subpage not in use (numAvail == maxNumElems)
      if (prev == next) {
        // Do not remove if this subpage is the only one left in the pool.
        return true;
      }

      // Remove this subpage from the pool if there are other subpages left in the pool.
      doNotDestroy = false;
      removeFromPool();
      return false;
    }
  }

  private void addToPool(PoolSubpage<T> head) {
    assert prev == null && next == null;
    prev = head;
    next = head.next;
    next.prev = this;
    head.next = this;
  }

  private void removeFromPool() {
    assert prev != null && next != null;
    prev.next = next;
    next.prev = prev;
    next = null;
    prev = null;
  }

  private void setNextAvail(int bitmapIdx) {
    nextAvail = bitmapIdx;
  }

  private int getNextAvail() {
    int nextAvail = this.nextAvail;
    if (nextAvail >= 0) {
      this.nextAvail = -1;
      return nextAvail;
    }
    return findNextAvail();
  }

  private int findNextAvail() {
    final long[] bitmap = this.bitmap;
    final int bitmapLength = this.bitmapLength;
    for (int i = 0; i < bitmapLength; i++) {
      long bits = bitmap[i];
      if (~bits != 0) {
        return findNextAvail0(i, bits);
      }
    }
    return -1;
  }

  private int findNextAvail0(int i, long bits) {
    final int maxNumElems = this.maxNumElems;
    final int baseVal = i << 6;

    for (int j = 0; j < 64; j++) {
      if ((bits & 1) == 0) {
        int val = baseVal | j;
        if (val < maxNumElems) {
          return val;
        } else {
          break;
        }
      }
      bits >>>= 1;
    }
    return -1;
  }

  private long toHandle(int bitmapIdx) {
    return 0x4000000000000000L | (long) bitmapIdx << 32 | memoryMapIdx;
  }

  @Override
  public String toString() {
    final boolean doNotDestroy;
    final int maxNumElems;
    final int numAvail;
    final int elemSize;
    synchronized (chunk.arena) {
      if (!this.doNotDestroy) {
        doNotDestroy = false;
        // Not used for creating the String.
        maxNumElems = numAvail = elemSize = -1;
      } else {
        doNotDestroy = true;
        maxNumElems = this.maxNumElems;
        numAvail = this.numAvail;
        elemSize = this.elemSize;
      }
    }

    if (!doNotDestroy) {
      return "(" + memoryMapIdx + ": not in use)";
    }

    return "(" + memoryMapIdx + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +
        ", offset: " + runOffset + ", length: " + pageSize + ", elemSize: " + elemSize + ')';
  }

  @Override
  public int maxNumElements() {
    synchronized (chunk.arena) {
      return maxNumElems;
    }
  }

  @Override
  public int numAvailable() {
    synchronized (chunk.arena) {
      return numAvail;
    }
  }

  @Override
  public int elementSize() {
    synchronized (chunk.arena) {
      return elemSize;
    }
  }

  @Override
  public int pageSize() {
    return pageSize;
  }

  void destroy() {
    if (chunk != null) {
      chunk.destroy();
    }
  }
}
